package com.summer.zuoChengYunBase;

import java.util.Arrays;

public class class_01 {
    //交换arr的i和j的值
    //0^N = N
    //N^N=0
    public static void swap(int[] arr,int i,int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
    //选择排序
    public static void chooseSort(){
        int[] arr = {3,2,7,1,6,9};
        int len = arr.length;
        for (int i = 0; i < len-1; i++) {
            int min = arr[i];
            int minIndex = -1;
            for (int j = i; j < len; j++) {
                if (arr[j]<min){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex>=0&&minIndex<=len-1){
                int swap = arr[i];
                arr[i] = min;
                arr[minIndex] = swap;
            }

        }
        System.out.println(Arrays.toString(arr));
    }
    //冒泡排序
    public static void maopao(){
        int[] arr = {3,2,7,1,6,9};
        int len = arr.length;
        for (int i = 0; i < len-1; i++) {
            for (int j = 0; j < len-i-1 ; j++) {
                if (arr[j]>arr[j+1]) swap(arr,j,j+1);
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    //插入排序
    public static void insertSort(){
        int[] arr = {3,2,7,1,6,9};
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            for (int j = i; j>0; j--) {
                if (arr[j]<arr[j-1])swap(arr,j,j-1);
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    //二分
    public static void binaryFind(){
        int[] arr = {1,2,3,4,5,6,7,8};
        int len = arr.length;
        int num = 5;
        int left = 0;
        int right = len-1;
        int mid = 0;
        boolean flag = true;
        while (left <= right){
             mid = (right+left)/2;
            if (arr[mid]==num){
                System.out.println("arr中找到num,下标为:"+mid);
                flag = !flag;
                break;
            }
            else if (arr[mid]<num){
                left = mid + 1;
            }
            else {
               right = mid - 1;
            }
        }
        if (flag)System.out.println("arr未找到num");
    }
    //arr中，有两种数出现奇数次
    public static void printOddTimeNum2(){
        int[] arr = {1,1,3,4,5,6,3,8,8,4};
        int len = arr.length;
        int eor = 0;
        for (int i = 0; i < len ; i++) {
            eor ^= arr[i];
        }
        //eor = a ^ b
        //eor != 0
        //eor必有一位上是1
        //0110010000
        //0000010000
        int rightOne = eor & (~eor + 1);//提取出最右边的1
        int onlyOne = 0;
        for (int i = 0; i < len ; i++) {
            if((arr[i]&rightOne)!=0){
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne+" "+(eor ^ onlyOne));
    }
    //提取一个数有多少位是1
    public static  void bit1counts(){
        int N = 16;
        int count = 0;
        while (N!=0){
            int rightOne = N & (~N +1);
            count ++;
            N ^= rightOne;
        }
        System.out.println(count);
    }
    public static void main(String[] args) {
        chooseSort();
        maopao();
        insertSort();
        binaryFind();
        printOddTimeNum2();
        bit1counts();
    }
}
